#include <iostream>
using namespace std;


struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}
};

//class Solution {
//public:
//    ListNode* reverseBetween(ListNode* head, int m, int n) {
//        // write code here
//        if (m == n)
//        {
//            return head;
//        }
//        ListNode* node = head;
//        ListNode* phead = nullptr;
//        ListNode* pphead = nullptr;
//        int k = m;
//        while (k--)
//        {
//            pphead = phead;
//            phead = node;
//            node = node->next;
//        }
//        k = n - m;
//        ListNode* pro = phead;
//        while (k--)
//        {
//            ListNode* next = node->next;
//            node->next = phead;
//            phead = node;
//            node = next;
//        }
//        pro->next = node;
//        if (pphead == nullptr)
//        {
//            return phead;
//        }
//        pphead->next = phead;
//        return head;
//    }
//};

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    // write code here
    if (pHead1 == NULL && pHead2 == NULL)
    {
        return NULL;
    }
    else if (pHead1 == NULL)
    {
        return pHead2;
    }
    else if (pHead2 == NULL)
    {
        return pHead1;
    }
    struct ListNode* ph = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p = ph;
    while (pHead1 && pHead2)
    {
        if (pHead1->val < pHead2->val)
        {
            ph->next = pHead1;
            ph = ph->next;
            pHead1 = pHead1->next;
        }
        else
        {
            ph->next = pHead2;
            ph = ph->next;
            pHead2 = pHead2->next;
        }
    }
    while (pHead1)
    {
        ph->next = pHead1;
        ph = ph->next;
        pHead1 = pHead1->next;
    }
    while (pHead2)
    {
        ph->next = pHead2;
        ph = ph->next;
        pHead2 = pHead2->next;
    }
    ph->next = NULL;
    return p->next;
}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:

    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        int len = 0;
        while (head)
        {
            head = head->next;
            len++;
        }
        for (int j = 0; j < len / k; j++)
        {
            for (int i = 1; i < k; i++)
            {
                ListNode* next = cur->next;
                cur->next = next->next;
                next->next = pre->next;
                pre->next = next;
            }
            pre = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* phead = new ListNode(0);
        phead->next = head;
        int i = 0;
        ListNode* node = head;
        ListNode* pphead = phead;
        ListNode* cur = phead;
        while (node)
        {
            i++;
            node = node->next;
        }
        node = head;
        while (i >= k)
        {
            for (int p = 1; p < k; p++)
            {
                pphead = node->next;
                node->next = pphead->next;
                pphead->next = cur->next;
                cur->next = pphead;
            }
            i -= k;
            cur = node;
            node = cur->next;
        }
        return phead->next;
    }
};

int main()
{
    ListNode* node = new ListNode(1);
    ListNode* head = node;
    node->next = new ListNode(2);
    node = node->next;
    node->next = new ListNode(3);
    node = node->next;
    node->next = new ListNode(4);
    node = node->next;
    node->next = new ListNode(5);
    Solution s;
    Print(s.reverseKGroup(head,2));
    return 0;
}